#define  _CRT_SECURE_NO_WARNINGS
/*
struct ListNode {
? ? int val;
? ? struct ListNode *next;
? ? ListNode(int x) : val(x), next(NULL) {}
};*/
#include <asm-generic/errno.h>
class Partition {
public:
	ListNode* partition(ListNode* pHead, int x) {
		ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
		ListNode* ptail1 = l1;
		ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
		ListNode* ptail2 = l2;
		ListNode* pcur = pHead;
		while (pcur)
		{
			if (pcur->val <= x)
			{
				ptail1->next = pcur;
				ptail1 = ptail1->next;
			}
			else {
				ptail2->next = pcur;
				ptail2 = ptail2->next;
			}
			pcur = pcur->next;
		}
		ptail2->next = NULL;
		ptail1->next = l2->next;
		ListNode* newhead = l1->next;
		free(l1);
		l1 = NULL;
		free(l2);
		l2 = NULL;
		return newhead;
	}
};